package com.copa.l90;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-18 10:34
 * @function 暴力法 去重使用HashSet简洁些
 */
public class Test2 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int resultLength = result.size();
            // 这里为啥不用直接遍历result，因为会报ConcurrentModificationException异常，如果想用，可以看subsetsWithDup2的
            for (int j = 0; j < resultLength; j++) {
                List<Integer> cur = new ArrayList<>(result.get(j));
                cur.add(nums[i]);
                result.add(cur);
            }
        }
        // 用Hashset去重，就不用标记法进行去重了
        HashSet<List<Integer>> set = new HashSet<>(result);
        return new ArrayList<>(set);
    }

    /**
     * 下面是我自己的解法 复杂化了用了map来标记
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 标记法，因为涉及到元素重复去重
        HashMap<List<Integer>, Boolean> map = new HashMap<>();
        // 先给nums排序
        Arrays.sort(nums);
        result.add(new ArrayList<>());
        for (int num : nums) {
            // 遍历当前num值
            List<List<Integer>> tempResult = new ArrayList<>();
            for (List<Integer> list : result) {
                // 从现有的结果集进行遍历，再添加所遍历的num值
                List<Integer> tempList = new ArrayList<>(list);
                tempList.add(num);
                if (Objects.isNull(map.get(tempList))) {
                    // 如果该数组没做标记，那么需要标记一下，再加入到临时结果集
                    map.put(tempList, true);
                    tempResult.add(tempList);
                }
            }
            for (List<Integer> list : tempResult) {
                // 汇总，加入到结果集中
                result.add(list);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 2};
        List<List<Integer>> result = new Test2().subsetsWithDup(nums);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

}
